Search Results

Documents authored by Sau, Ignasi

Document
DOI: 10.4230/LIPIcs.IPEC.2023.26
Dynamic Programming on Bipartite Tree Decompositions

Authors: Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one vertex from the bipartite part of any other bag, while the width of such decomposition measures how far the bags are from being bipartite. Adapted from a tree decomposition originally defined by Demaine, Hajiaghayi, and Kawarabayashi [SODA 2010] and explicitly defined by Tazari [Theor. Comput. Sci. 2012], bipartite treewidth appears to play a crucial role for solving problems related to odd-minors, which have recently attracted considerable attention. As a first step toward a theory for solving these problems efficiently, the main goal of this paper is to develop dynamic programming techniques to solve problems on graphs of small bipartite treewidth. For such graphs, we provide a number of para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that K_t-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are FPT parameterized by bipartite treewidth. We also provide the following complexity dichotomy when H is a 2-connected graph, for each of the H-Subgraph-Packing, H-Induced-Packing, H-Scattered-Packing, and H-Odd-Minor-Packing problems: if H is bipartite, then the problem is para-NP-complete parameterized by bipartite treewidth while, if H is non-bipartite, then the problem is solvable in XP-time. Beyond bipartite treewidth, we define 1-ℋ-treewidth by replacing the bipartite graph class by any graph class ℋ. Most of the technology developed here also works for this more general parameter.
Cite as

Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos. Dynamic Programming on Bipartite Tree Decompositions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2023.26,
  author =	{Jaffke, Lars and Morelle, Laure and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Dynamic Programming on Bipartite Tree Decompositions}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.26},
  URN =		{urn:nbn:de:0030-drops-194455},
  doi =		{10.4230/LIPIcs.IPEC.2023.26},
  annote =	{Keywords: tree decomposition, bipartite graphs, dynamic programming, odd-minors, packing, maximum cut, vertex cover, independent set, odd cycle transversal}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.30
New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages

Authors: Victor Campos, Jonas Costa, Raul Lopes, and Ignasi Sau

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving the half-integral linkage problem, the essential properties needed for reaching a large bramble of congestion two (or any other constant) from the terminal set. This strategy has been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max relations, one consisting in applying Menger’s Theorem on appropriately defined auxiliary digraphs, and an alternative simpler one using matroids, however with worse polynomial running time. As an application, we manage to simplify and improve several results of Edwards et al. [ESA 2017] and of Giannopoulou et al. [SODA 2022] about finding half-integral linkages in digraphs. Concerning the former, besides being simpler, our proof provides an almost optimal bound on the strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed tree-width is large, which is the hard case). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical grids, hence yielding much better bounds and being somehow independent of a particular topology. We hope that our min-max relations will find further applications as, in our opinion, they are simple, robust, and versatile to be easily applicable to different types of routing problems in digraphs.
Cite as

Victor Campos, Jonas Costa, Raul Lopes, and Ignasi Sau. New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{campos_et_al:LIPIcs.ESA.2023.30,
  author =	{Campos, Victor and Costa, Jonas and Lopes, Raul and Sau, Ignasi},
  title =	{{New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.30},
  URN =		{urn:nbn:de:0030-drops-186838},
  doi =		{10.4230/LIPIcs.ESA.2023.30},
  annote =	{Keywords: directed graphs, min-max relation, half-integral linkage, directed disjoint paths, bramble, parameterized complexity, matroids}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.61
Compound Logics for Modification Problems

Authors: Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or G-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply.
Cite as

Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound Logics for Modification Problems. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 61:1-61:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ICALP.2023.61,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Sau, Ignasi and Stamoulis, Giannos and Thilikos, Dimitrios M.},
  title =	{{Compound Logics for Modification Problems}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{61:1--61:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.61},
  URN =		{urn:nbn:de:0030-drops-181137},
  doi =		{10.4230/LIPIcs.ICALP.2023.61},
  annote =	{Keywords: Algorithmic meta-theorems, Graph modification problems, Model-checking, Graph minors, First-order logic, Monadic second-order logic, Flat Wall theorem, Irrelevant vertex technique}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.93
Faster Parameterized Algorithms for Modification Problems to Minor-Closed Classes

Authors: Laure Morelle, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Let G be a minor-closed graph class and let G be an n-vertex graph. We say that G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. Our first result is an algorithm that decides whether G is a k-apex of G in time 2^poly(k)⋅n². This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020, TALG 2022], whose running time was 2^poly(k)⋅n³. The elimination distance of G to G, denoted by ed_G(G), is the minimum number of rounds required to reduce each connected component of G to a graph in G by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] proved the existence of an FPT-algorithm, with parameter k, to decide whether ed_G(G) ≤ k. This algorithm is based on the computability of the minor-obstructions and its dependence on k is not explicit. We extend the techniques used in the first algorithm to decide whether ed_G(G) ≤ k in time 2^{2^{2^poly(k)}}⋅n². This is the first algorithm for this problem with an explicit parametric dependence in k. In the special case where G excludes some apex-graph as a minor, we give two alternative algorithms, one running in time 2^{2^O(k²log k)}⋅n² and one running in time 2^{poly(k)}⋅n³. As a stepping stone for these algorithms, we provide an algorithm that decides whether ed_G(G) ≤ k in time 2^O(tw⋅ k + tw log tw)⋅n, where tw is the treewidth of G. This algorithm combines the dynamic programming framework of Reidl, Rossmanith, Villaamil, and Sikdar [ICALP 2014] for the particular case where G contains only the empty graph (i.e., for treedepth) with the representative-based techniques introduced by Baste, Sau, and Thilikos [SODA 2020]. In all the algorithmic complexities above, poly is a polynomial function whose degree depends on G, while the hidden constants also depend on G. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs E_k(G) = {G ∣ ed_G(G) ≤ k}.
Cite as

Laure Morelle, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Faster Parameterized Algorithms for Modification Problems to Minor-Closed Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 93:1-93:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{morelle_et_al:LIPIcs.ICALP.2023.93,
  author =	{Morelle, Laure and Sau, Ignasi and Stamoulis, Giannos and Thilikos, Dimitrios M.},
  title =	{{Faster Parameterized Algorithms for Modification Problems to Minor-Closed Classes}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{93:1--93:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.93},
  URN =		{urn:nbn:de:0030-drops-181458},
  doi =		{10.4230/LIPIcs.ICALP.2023.93},
  annote =	{Keywords: Graph minors, Parameterized algorithms, Graph modification problems, Vertex deletion, Elimination distance, Irrelevant vertex technique, Flat Wall Theorem, Obstructions}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.69
Reducing the Vertex Cover Number via Edge Contractions

Authors: Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza, and Prafullkumar Tale

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
The Contraction(vc) problem takes as input a graph G on n vertices and two integers k and d, and asks whether one can contract at most k edges to reduce the size of a minimum vertex cover of G by at least d. Recently, Lima et al. [MFCS 2020, JCSS 2021] proved, among other results, that unlike most of the so-called blocker problems, Contraction(vc) admits an XP algorithm running in time f(d) ⋅ n^O(d). They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results: - Contraction(vc) is W[1]-hard parameterized by k + d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f(k + d) ⋅ n^o(k + d) for any function f. In particular, this answers the open question stated in Lima et al. [MFCS 2020] in the negative. - It is NP-hard to decide whether an instance (G, k, d) of {Contraction(vc)} is a Yes-instance even when k = d, hence enhancing our understanding of the classical complexity of the problem. - Contraction(vc) can be solved in time 2^O(d) ⋅ n^{k - d + O(1)}. This XP algorithm improves the one of Lima et al. [MFCS 2020], which uses Courcelle’s theorem as a subroutine and hence, the f(d)-factor in the running time is non-explicit and probably very large. On the other hand, this shows that when k = d, the problem is FPT parameterized by d (or by k).
Cite as

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza, and Prafullkumar Tale. Reducing the Vertex Cover Number via Edge Contractions. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lima_et_al:LIPIcs.MFCS.2022.69,
  author =	{Lima, Paloma T. and dos Santos, Vinicius F. and Sau, Ignasi and Souza, U\'{e}verton S. and Tale, Prafullkumar},
  title =	{{Reducing the Vertex Cover Number via Edge Contractions}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.69},
  URN =		{urn:nbn:de:0030-drops-168671},
  doi =		{10.4230/LIPIcs.MFCS.2022.69},
  annote =	{Keywords: Blocker problems, edge contraction, vertex cover, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.4
A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover

Authors: Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain lower bounds on the degrees of a certain type of polynomial kernels for vertex-optimization problems, which we call {lop-kernels}. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. On the positive side, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdős-Hajnal property in order to find an appropriate decomposition. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless NP ⊆ coNP / poly. This indicates that parameters smaller than the solution size are unlike to yield polynomial kernels for MMVC.
Cite as

Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau. A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.IPEC.2021.4,
  author =	{Ara\'{u}jo, J\'{u}lio and Bougeret, Marin and Campos, Victor and Sau, Ignasi},
  title =	{{A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.4},
  URN =		{urn:nbn:de:0030-drops-153879},
  doi =		{10.4230/LIPIcs.IPEC.2021.4},
  annote =	{Keywords: Maximum minimal vertex cover, parameterized complexity, polynomial kernel, kernelization lower bound, Erd\H{o}s-Hajnal property, induced subgraphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.64
Reducing Graph Transversals via Edge Contractions

Authors: Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, and Uéverton S. Souza

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where π is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection ℋ according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in ℋ, which in particular imply that Contraction(π) is co-NP-hard even for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when π is the size of a minimum vertex cover, the problem is in XP parameterized by d.
Cite as

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, and Uéverton S. Souza. Reducing Graph Transversals via Edge Contractions. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lima_et_al:LIPIcs.MFCS.2020.64,
  author =	{Lima, Paloma T. and dos Santos, Vinicius F. and Sau, Ignasi and Souza, U\'{e}verton S.},
  title =	{{Reducing Graph Transversals via Edge Contractions}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{64:1--64:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.64},
  URN =		{urn:nbn:de:0030-drops-127346},
  doi =		{10.4230/LIPIcs.MFCS.2020.64},
  annote =	{Keywords: blocker problem, edge contraction, graph transversal, parameterized complexity, vertex cover, feedback vertex set, odd cycle transversal}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.68
A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps

Authors: Raul Lopes and Ignasi Sau

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
In the Directed Disjoint Paths problem, we are given a digraph D and a set of requests {(s₁, t₁), …, (s_k, t_k)}, and the task is to find a collection of pairwise vertex-disjoint paths {P₁, …, P_k} such that each P_i is a path from s_i to t_i in D. This problem is NP-complete for fixed k = 2 and W[1]-hard with parameter k in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Good news are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified large part of it. Namely, in the Disjoint Enough Directed Paths problem, given an n-vertex digraph D, a set of k requests, and non-negative integers d and s, the task is to find a collection of paths connecting the requests such that at least d vertices of D occur in at most s paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of D. Among other results, we show that the problem is W[1]-hard in DAGs with parameter d and, on the positive side, we give an algorithm in time 𝒪(n^{d+2} ⋅ k^{d⋅ s}) and a kernel of size d ⋅ 2^{k-s}⋅ binom(k,s) + 2k in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number k of terminals and d, where d = n - c and c is the size of the solution.
Cite as

Raul Lopes and Ignasi Sau. A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lopes_et_al:LIPIcs.MFCS.2020.68,
  author =	{Lopes, Raul and Sau, Ignasi},
  title =	{{A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.68},
  URN =		{urn:nbn:de:0030-drops-127378},
  doi =		{10.4230/LIPIcs.MFCS.2020.68},
  annote =	{Keywords: Parameterized complexity, directed disjoint paths, congestion, dual parameterization, kernelization, directed tree-width}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.82
Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs

Authors: Ignasi Sau and Uéverton dos Santos Souza

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, for the minimum size of a set S ⊆ V(G) such that G⧵ S does not contain H as an induced subgraph. Motivated by previous work about hitting (topological) minors and subgraphs on bounded treewidth graphs, we are interested in determining, for a fixed graph H, the smallest function f_H(t) such that H-IS-Deletion can be solved in time f_H(t) ⋅ n^{𝒪(1)} assuming the Exponential Time Hypothesis (ETH), where t and n denote the treewidth and the number of vertices of the input graph, respectively. We show that f_H(t) = 2^{𝒪(t^{h-2})} for every graph H on h ≥ 3 vertices, and that f_H(t) = 2^{𝒪(t)} if H is a clique or an independent set. We present a number of lower bounds by generalizing a reduction of Cygan et al. [MFCS 2014] for the subgraph version. In particular, we show that when H deviates slightly from a clique, the function f_H(t) suffers a sharp jump: if H is obtained from a clique of size h by removing one edge, then f_H(t) = 2^{Θ(t^{h-2})}. We also show that f_H(t) = 2^{Ω(t^{h})} when H = K_{h,h}, and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function f_{C₄}(t) for the subgraph version. Motivated by Cygan et al. [MFCS 2014], we also consider the colorful variant of the problem, where each vertex of G is colored with some color from V(H) and we require to hit only induced copies of H with matching colors. In this case, we determine, under the ETH, the function f_H(t) for every connected graph H on h vertices: if h ≤ 2 the problem can be solved in polynomial time; if h ≥ 3, f_H(t) = 2^{Θ(t)} if H is a clique, and f_H(t) = 2^{Θ(t^{h-2})} otherwise.
Cite as

Ignasi Sau and Uéverton dos Santos Souza. Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sau_et_al:LIPIcs.MFCS.2020.82,
  author =	{Sau, Ignasi and Souza, U\'{e}verton dos Santos},
  title =	{{Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{82:1--82:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.82},
  URN =		{urn:nbn:de:0030-drops-127511},
  doi =		{10.4230/LIPIcs.MFCS.2020.82},
  annote =	{Keywords: parameterized complexity, induced subgraphs, treewidth, hitting subgraphs, dynamic programming, lower bound, Exponential Time Hypothesis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.16
Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel

Authors: Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can reduce any instance (G,k) of the Vertex Cover problem to an equivalent one, whose size is polynomial in the size of a pre-determined complexity parameter of G. A long line of previous research deals with parameterizations based on the number of vertex deletions needed to reduce G to a member of a simple graph class ℱ, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes ℱ for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to ℱ, admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families ℱ for which such a kernelization exists. We introduce a new graph parameter called bridge-depth, and prove that a polynomial kernelization exists if and only if ℱ has bounded bridge-depth. The proof is based on an interesting connection between bridge-depth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number.
Cite as

Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bougeret_et_al:LIPIcs.ICALP.2020.16,
  author =	{Bougeret, Marin and Jansen, Bart M. P. and Sau, Ignasi},
  title =	{{Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.16},
  URN =		{urn:nbn:de:0030-drops-124238},
  doi =		{10.4230/LIPIcs.ICALP.2020.16},
  annote =	{Keywords: vertex cover, parameterized complexity, polynomial kernel, structural parameterization, bridge-depth}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.95
An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes

Authors: Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Let G be a graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. We prove that if G is minor-closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2^{poly(k)}n³ time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of graphs not belonging to G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2^{poly(k)}n² time.
Cite as

Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sau_et_al:LIPIcs.ICALP.2020.95,
  author =	{Sau, Ignasi and Stamoulis, Giannos and Thilikos, Dimitrios M.},
  title =	{{An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{95:1--95:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.95},
  URN =		{urn:nbn:de:0030-drops-125027},
  doi =		{10.4230/LIPIcs.ICALP.2020.95},
  annote =	{Keywords: Graph modification problems, irrelevant vertex technique, graph minors, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.19
Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization

Authors: Guilherme C. M. Gomes and Ignasi Sau

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
A matching cut is a partition of the vertex set of a graph into two sets A and B such that each vertex has at most one neighbor in the other side of the cut. The Matching Cut problem asks whether a graph has a matching cut, and has been intensively studied in the literature. Motivated by a question posed by Komusiewicz et al. [IPEC 2018], we introduce a natural generalization of this problem, which we call d-Cut: for a positive integer d, a d-cut is a bipartition of the vertex set of a graph into two sets A and B such that each vertex has at most d neighbors across the cut. We generalize (and in some cases, improve) a number of results for the Matching Cut problem. Namely, we begin with an NP-hardness reduction for d-Cut on (2d+2)-regular graphs and a polynomial algorithm for graphs of maximum degree at most d+2. The degree bound in the hardness result is unlikely to be improved, as it would disprove a long-standing conjecture in the context of internal partitions. We then give FPT algorithms for several parameters: the maximum number of edges crossing the cut, treewidth, distance to cluster, and distance to co-cluster. In particular, the treewidth algorithm improves upon the running time of the best known algorithm for Matching Cut. Our main technical contribution, building on the techniques of Komusiewicz et al. [IPEC 2018], is a polynomial kernel for d-Cut for every positive integer d, parameterized by the distance to a cluster graph. We also rule out the existence of polynomial kernels when parameterizing simultaneously by the number of edges crossing the cut, the treewidth, and the maximum degree. Finally, we provide an exact exponential algorithm slightly faster than the naive brute force approach running in time O^*(2^n).
Cite as

Guilherme C. M. Gomes and Ignasi Sau. Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2019.19,
  author =	{C. M. Gomes, Guilherme and Sau, Ignasi},
  title =	{{Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.19},
  URN =		{urn:nbn:de:0030-drops-114809},
  doi =		{10.4230/LIPIcs.IPEC.2019.19},
  annote =	{Keywords: matching cut, bounded degree cut, parameterized complexity, FPT algorithm, polynomial kernel, distance to cluster}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.2
A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth

Authors: Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
For a fixed graph H, we are interested in the parameterized complexity of the following problem, called {H}-M-Deletion, parameterized by the treewidth tw of the input graph: given an n-vertex graph G and an integer k, decide whether there exists S subseteq V(G) with |S| <= k such that G setminus S does not contain H as a minor. In previous work [IPEC, 2017] we proved that if H is planar and connected, then the problem cannot be solved in time 2^{o(tw)} * n^{O(1)} under the ETH, and can be solved in time 2^{O(tw * log tw)} * n^{O(1)}. In this article we manage to classify the optimal asymptotic complexity of {H}-M-Deletion when H is a connected planar graph on at most 5 vertices. Out of the 29 possibilities (discarding the trivial case H = K_1), we prove that 9 of them are solvable in time 2^{Theta (tw)} * n^{O(1)}, and that the other 20 ones are solvable in time 2^{Theta (tw * log tw)} * n^{O(1)}. Namely, we prove that K_4 and the diamond are the only graphs on at most 4 vertices for which the problem is solvable in time 2^{Theta (tw * log tw)} * n^{O(1)}, and that the chair and the banner are the only graphs on 5 vertices for which the problem is solvable in time 2^{Theta (tw)} * n^{O(1)}. For the version of the problem where H is forbidden as a topological minor, the case H = K_{1,4} can be solved in time 2^{Theta (tw)} * n^{O(1)}. This exhibits, to the best of our knowledge, the first difference between the computational complexity of both problems.
Cite as

Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{baste_et_al:LIPIcs.IPEC.2018.2,
  author =	{Baste, Julien and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{2:1--2:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.2},
  URN =		{urn:nbn:de:0030-drops-102033},
  doi =		{10.4230/LIPIcs.IPEC.2018.2},
  annote =	{Keywords: parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.12
Dual Parameterization of Weighted Coloring

Authors: Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
Given a graph G, a proper k-coloring of G is a partition c = (S_i)_{i in [1,k]} of V(G) into k stable sets S_1,..., S_k. Given a weight function w: V(G) -> R^+, the weight of a color S_i is defined as w(i) = max_{v in S_i} w(v) and the weight of a coloring c as w(c) = sum_{i=1}^{k} w(i). Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair (G,w), denoted by sigma(G,w), as the minimum weight of a proper coloring of G. The problem of determining sigma(G,w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time n^{o(log n)} unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G,w) and an integer k, is sigma(G,w) <= sum_{v in V(G)} w(v) - k? This parameterization has been recently considered by Escoffier [WG, 2016], who provided an FPT algorithm running in time 2^{O(k log k)} * n^{O(1)}, and asked which kernel size can be achieved for the problem. We provide an FPT algorithm running in time 9^k * n^{O(1)}, and prove that no algorithm in time 2^{o(k)} * n^{O(1)} exists under the ETH. On the other hand, we present a kernel with at most (2^{k-1}+1) (k-1) vertices, and rule out the existence of polynomial kernels unless NP subseteq coNP/poly, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.
Cite as

Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva. Dual Parameterization of Weighted Coloring. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.IPEC.2018.12,
  author =	{Ara\'{u}jo, J\'{u}lio and Campos, Victor A. and Lima, Carlos Vin{\'\i}cius G. C. and Fernandes dos Santos, Vin{\'\i}cius and Sau, Ignasi and Silva, Ana},
  title =	{{Dual Parameterization of Weighted Coloring}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.12},
  URN =		{urn:nbn:de:0030-drops-102134},
  doi =		{10.4230/LIPIcs.IPEC.2018.12},
  annote =	{Keywords: weighted coloring, max coloring, parameterized complexity, dual parameterization, FPT algorithms, polynomial kernels, split graphs, interval graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.3
Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter

Authors: Julien Baste, Didem Gözüpek, Christophe Paul, Ignasi Sau, Mordechai Shalom, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that DIAMETER-TREE is para-np-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with Delta=3, and Galbiati (2008) proved that it is NP-hard if Delta=4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta=3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus Delta.
Cite as

Julien Baste, Didem Gözüpek, Christophe Paul, Ignasi Sau, Mordechai Shalom, and Dimitrios M. Thilikos. Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{baste_et_al:LIPIcs.IPEC.2017.3,
  author =	{Baste, Julien and G\"{o}z\"{u}pek, Didem and Paul, Christophe and Sau, Ignasi and Shalom, Mordechai and Thilikos, Dimitrios M.},
  title =	{{Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{3:1--3:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.3},
  URN =		{urn:nbn:de:0030-drops-85545},
  doi =		{10.4230/LIPIcs.IPEC.2017.3},
  annote =	{Keywords: reload cost problems, minimum diameter spanning tree, parameterized complexity, FPT algorithm, treewidth, dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.4
Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth

Authors: Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
For a fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists a subset S of V(G) of size at most k such that G-S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-DELETION when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F}, the smallest function f_F such that F-M-DELETION can be solved in time f_F(tw)n^{O(1)} on n-vertex graphs. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_F(w) = 2^{O(wlog w)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds: - f_{K_4}(w) = 2^{Theta(wlog w)}. - f_{C_i}(w) = 2^{Theta(w)} for every i<5, and f_{C_i}(w) = 2^{Theta(wlog w)} for every i>4. - f_{P_i}(w) = 2^{Theta(w)} for every i<5, and f_{P_i}(w) = 2^{Theta(wlog w)} for every i>5. The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The single-exponential algorithms use, in particular, the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.
Cite as

Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{baste_et_al:LIPIcs.IPEC.2017.4,
  author =	{Baste, Julien and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.4},
  URN =		{urn:nbn:de:0030-drops-85556},
  doi =		{10.4230/LIPIcs.IPEC.2017.4},
  annote =	{Keywords: parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.10
How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?

Authors: Marin Bougeret and Ignasi Sau

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsky et al. [ESA 2013] proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a c-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most c for a fixed integer c>0. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs. In this article we answer this question by finding two very natural such problems: we prove that VERTEX COVER admits a polynomial kernel on general graphs for any integer c>0, and that DOMINATING SET does not for any integer c>1 even on degenerate graphs, unless NP is a subset of coNP/poly. For the positive result, we build on the techniques of Jansen and Bodlaender [STACS 2011], and for the negative result we use a polynomial parameter transformation for c>2 and an OR-cross-composition for c=2. As existing results imply that DOMINATING SET admits a polynomial kernel on degenerate graphs for c=1, our result provides a dichotomy about the existence of polynomial problems for DOMINATING SET on degenerate graphs with this parameter.
Cite as

Marin Bougeret and Ignasi Sau. How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bougeret_et_al:LIPIcs.IPEC.2017.10,
  author =	{Bougeret, Marin and Sau, Ignasi},
  title =	{{How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.10},
  URN =		{urn:nbn:de:0030-drops-85564},
  doi =		{10.4230/LIPIcs.IPEC.2017.10},
  annote =	{Keywords: parameterized complexity, polynomial kernels, structural parameters, treedepth, treewidth, sparse graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.78
Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism

Authors: Eun Jung Kim, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
In this paper we design FPT-algorithms for two parameterized problems. The first is List Digraph Homomorphism: given two digraphs G and H and a list of allowed vertices of H for every vertex of G, the question is whether there exists a homomorphism from G to H respecting the list constraints. The second problem is a variant of Multiway Cut, namely Min-Max Multiway Cut: given a graph G, a non-negative integer l, and a set T of r terminals, the question is whether we can partition the vertices of G into r parts such that (a) each part contains one terminal and (b) there are at most l edges with only one endpoint in this part. We parameterize List Digraph Homomorphism by the number w of edges of G that are mapped to non-loop edges of H and we give a time 2^{O(l * log(h) + l^{2 * log(l)}} * n^{4} * log(n) algorithm, where h is the order of the host graph H.We also prove that Min-Max Multiway Cut can be solved in time 2^{O((l * r)^2 * log(l *r))} * n^{4} * log(n). Our approach introduces a general problem, called List Allocation, whose expressive power permits the design of parameterized reductions of both aforementioned problems to it. Then our results are based on an FPT-algorithm for the List Allocation problem that is designed using a suitable adaptation of the randomized contractions technique (introduced by [Chitnis, Cygan, Hajiaghayi, Pilipczuk, and Pilipczuk, FOCS 2012]).
Cite as

Eun Jung Kim, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 78-89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.IPEC.2015.78,
  author =	{Kim, Eun Jung and Paul, Christophe and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{78--89},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.78},
  URN =		{urn:nbn:de:0030-drops-55738},
  doi =		{10.4230/LIPIcs.IPEC.2015.78},
  annote =	{Keywords: Parameterized complexity, Fixed-Parameter Tractable algorithm, Multiway Cut, Digraph homomorphism}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.312
Explicit Linear Kernels via Dynamic Programming

Authors: Valentin Garnero, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result [Bodlaender et al., FOCS 2009] on graphs of bounded genus, then generalized by [Fomin et al., SODA 2010] to graphs excluding a fixed minor, and by [Kim et al., ICALP 2013] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in CMSO logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-Dominating Set and r-Scattered Set on apex-minor-free graphs, and for Planar-F-Deletion on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected.
Cite as

Valentin Garnero, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. Explicit Linear Kernels via Dynamic Programming. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 312-324, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{garnero_et_al:LIPIcs.STACS.2014.312,
  author =	{Garnero, Valentin and Paul, Christophe and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Explicit Linear Kernels via Dynamic Programming}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{312--324},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.312},
  URN =		{urn:nbn:de:0030-drops-44675},
  doi =		{10.4230/LIPIcs.STACS.2014.312},
  annote =	{Keywords: parameterized complexity, linear kernels, dynamic programming, protrusion replacement, graph minors}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2487
The Recognition of Tolerance and Bounded Tolerance Graphs

Authors: George B. Mertzios, Ignasi Sau, and Shmuel Zaks

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs --~namely, the problem of deciding whether a given graph is a tolerance graph~-- as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf.~the book on tolerance graphs~\cite{GolTol04}) since their introduction in 1982~\cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs~\cite{MC-Trapezoid}.
Cite as

George B. Mertzios, Ignasi Sau, and Shmuel Zaks. The Recognition of Tolerance and Bounded Tolerance Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 585-596, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.STACS.2010.2487,
  author =	{Mertzios, George B. and Sau, Ignasi and Zaks, Shmuel},
  title =	{{The Recognition of Tolerance and Bounded Tolerance Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{585--596},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2487},
  URN =		{urn:nbn:de:0030-drops-24876},
  doi =		{10.4230/LIPIcs.STACS.2010.2487},
  annote =	{Keywords: Tolerance graphs, bounded tolerance graphs, recognition, vertex splitting, NP-complete, trapezoid graphs, permutation graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact